94. 二叉树的中序遍历

// 给定一个二叉树的根节点 root ，返回它的 中序 遍历。
var inorderTraversal = function(root) {
  // const res = []

  // function dfs(val) {
  //   if (!val) return
  //   dfs(val.left)
  //   res.push(val.val)
  //   dfs(val.right)
  // }

  // dfs(root)

  // return res

  const res = []
  const stack = []

  while (root || stack.length) {
    while (root) {
      stack.push(root)
      root = root.left
    }
    const r = stack.pop()
    res.push(r.val)
    root = r.right
  }

  return res
}
console.log(
  inorderTraversal({
    val: 1,
    left: null,
    right: {
      val: 2,
      left: {
        val: 3,
      },
      rightL: null,
    },
  })
)